package offer;

public class offer07 {
    public  static TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||inorder==null) return null;
         TreeNode root= build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
        return root;
    }

    private static TreeNode build(int[] preorder, int leftpr, int rightpr, int[] inorder, int leftin, int rightin) {
        if(leftpr>rightpr||leftin>rightin) return null;
        int index = 0;
        for (int i = leftin; i <=rightin ; i++) {
            if(preorder[leftpr]==inorder[i])
            {
                index = i;
                break;
            }
        }
        TreeNode root = new TreeNode(preorder[leftpr]);
        int len = index - leftin;
        root.left = build(preorder,leftpr+1,leftpr+len,inorder,leftin,index-1);
        root.right = build(preorder,leftpr+len+1,rightpr,inorder,index+1,rightin);
    return root;
    }

    public static void main(String[] args) {
        int []pre ={3,9,6,20,15,7};
        int []in = {9,6,3,15,20,7};
        buildTree(pre,in);
    }
}
